COMMENT ⊗   VALID 00017 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	PAGE 21. FIGURES.
C00004 00003	PAGE 22. THE ALGORITHM:	INTRODUCTION.
C00006 00004	PAGE 23. FIGURES.
C00007 00005	PAGE 24. 1. THRESHOLDING.
C00009 00006	PAGE 25. FIGURES. DEKINKING ILLUSTRATED.
C00010 00007	PAGE 26. 2. CONTOURING.
C00015 00008	PAGE 27. FIGURES: NESTING ILLUSTRATED.
C00016 00009	PAGE 28. 3. NESTING.
C00021 00010	PAGE 29. NESTING ILLUSTRATED. CONTINUED.
C00022 00011	PAGE 30. NESTING CONTINUED.
C00023 00012	PAGE 31. FIGURES: RECURSIVE SMOOTHING ILLUSTRATED.
C00024 00013	PAGE 32. 4. SMOOTHING.
C00027 00014	PAGE 33. FIGURES: COMPARING ILLUSTRATED.
C00028 00015	PAGE 34. 5. COMPARING.
C00030 00016	PAGE 35. LAMINA INERTIA TENSOR.
C00031 00017	PAGE 36. PERFORMANCE.
C00032 ENDMK
C⊗;
PAGE 21. FIGURES.
	PUMP VIDEO
	PUMP CONTOURS
PAGE 22. THE ALGORITHM:	INTRODUCTION.

	CRE  consists  of  five  steps:  thresholding,    contouring,
nesting,   smoothing and  comparing.  The  first,   second and fourth
steps perform  conversions  between two  different kinds  of  images;
while   the   third  and   the   fifth   steps  compute   topological
relationships within a given image representation.

	MAJOR OPERATION.	OPERAND.	  RESULT.

	1. THRESHOLDING: 	6-BIT-IMAGE,	  1-BIT-IMAGES.
	2. CONTOURING: 	 	1-BIT-IMAGES,	  VIC-IMAGE.
	3. NESTING:		VIC-IMAGE,	  NESTED-VIC-IMAGE.
	4. SMOOTHING:	 	VIC-IMAGE,	  ARC-IMAGE.
	5. COMPARING:		IMAGE & FILM,	  FILM.

PAGE 23. FIGURES.
DBA'S TOMBSTONE VIDEO.
DBA'S SMOOTHED CONTOURS.
PAGE 24. 1. THRESHOLDING.

	Thresholding, the  first and easiest  step,  consists  of two
subroutines,    called THRESH  and  PACXOR. THRESH  converts  a 6-bit
image into a 1-bit image with respect to a given threshold  cut level
between zero  for black and sixty  three for light. All  pixels equal
to or  greater than the cut, map into a one; all the pixels less than
the cut, map into zero. The resulting 1-bit image is  stored in a bit
array  of  216  rows by  288  columns  (1728  words) called  the  PAC
(picture accumulator)  which is  supposed to  remind  one  of
McCormick's ILLIAC-III.  After  THRESH,   the PAC  contains blobs  of
bits.

	Next,   PACXOR copies  the PAC  into two slightly  larger bit
arrays named HSEG and VSEG. Then the PAC is displaced one row  or one
column, and  is exclusive  OR'ed into  HSEG and  VSEG to  compute the
horizontal  and vertical border bits of the  PAC blobs.  Notice, that
this is the very heart  of the "edge finder" of CRE. Namely,   PACXOR
is the mechanism that converts regions into edges.
PAGE 25. FIGURES. DEKINKING ILLUSTRATED.
PAGE 26. 2. CONTOURING.

	Contouring,   converts  the  bit arrays  HSEG  and VSEG  into
vectors  and polygons.  The  contouring itself,  is  done by a single
subroutine named MKPGON,  make polygon.   When MKPGON is called,   it
looks for the upper most left non-zero  bit in the VSEG array. If the
VSEG  array is empty, MKPGON returns a  NIL. However, when the bit is
found, MKPGON traces and  erases the polygonal outline to  which that
bit belongs  and returns  a polygon node  with a ring  of appropriate
vectors.

	To belabor the details (for the sake of later  complexities);
the MKGON  trace can  go in  four directions:  north and south  along
vertical  columns of bits in  the VSEG array, or  east and west along
horizontal rows of the  HSEG array. Now  the trace starts by  heading
south until  it hits a "turn";  when heading south MKPGON  must check
for  first a turn to the east (indicated  by a bit in HSEG); next for
no turn (continue  south); and last  for a turn  to the west. When  a
turn  is encountered MKPGON  creates a  vector node  representing the
run of bits  between the  previous turn and  the present  turn.   The
trace always ends heading  west bound.  The outline so  traced can be
either the edge of  a blob or a hole, the two cases are distinguished
by looking at the VIC-polygon's upper left most pixel in the  PAC bit
array.

	There are two complexities: contrast
accumulation  and dekinking. The contrast  of a vector  is defined as
(QUOTIENT (DIFFERENCE  (Sum  of  pixel  values on  one  side  of  the
vector)(Sum of pixel values on  the other side ofthe vector)) (length
of  the  vector  in  pixels)).    Since  vectors  are  always  either
horizontal or  vertical  and are  construed as  being  on the  cracks
between pixels;  the require summations  refer to the  obvious pixels
squares on either side of the vector. Notice that this definition  of
constrast will  always give  a positive  constrast for  vectors of  a
blob  and  negative   contrast  for  the  vectors  of  a  hole.  More
sophisticated definitions  of vector  constrast lack  this  desirable
property.

	Finally, dekinking refers to cutting  the corners in order to
avoid the  jaggies. The jaggies problem involves doing something to a
rectilinear quantized  set of segments,   to  make its linear  nature
more evident. The jaggies  solution in MKPGON merely involves vernier
positioning the turning locus alittle  to the northeast,   northwest,
southwest or  southeast. The amount  of dekinking vernier  is greater
for brighter cuts  and less for the darker cuts; in order to preserve
the nesting of contours.
PAGE 27. FIGURES: NESTING ILLUSTRATED.
1ST FRAME FLAT NEST.
2ND FRAME GEOMED NEST.

PAGE 28. 3. NESTING.

	The nesting problem is to decide  whether one contour polygon
is  within another.  Although  easy in the two  polygon case; solving
the nesting  of many  polygons  with respect  to each  other  becomes
n-squared expensive in  either compute time or in memory  space.  The
nesting  solution in CRE  sacrifices memory for speed  and requires a
31K array, called the SKY.

	CRE's accumulation  of a  properly  nested  tree  of  polygons
depends on the  order of threshold cutting going  from dark to light.
For each polygon there  are two  nesting steps: first, the polygon  is
placed in  the  tree of  nested polygons  by  the subroutine  INTREE;
second,  the polygon  is placed  in the SKY  array by  the subroutine
named INSKY.

	The SKY array is 216 rows of 288 columns of  18-bit pointers.
The name "SKY"  came about because,  the array  used to represent the
furthest  away regions or  background, which  in the case  of a robot
vehicle is the  real sky  blue. The sky  contains vector pointers;
and  would be very efficient  on on a  virtual memory machine
that didn't  allocate unused  pages of  its address  space.   Whereas
most  computers  have  more memory  containers  than  address  space;
computer graphics  and vision might be easier  to program in a memory
with more address apace than physical space; i.e. an almost  empty virtual
memory.

	The naive INTREE routine finds the  surrounder of a  given polygon
by  scanning the SKY due  east from the upper left  most pixel of the
given polygon. The SON of  a polygon is always its  uppermost left
vector. And next the INSKY routine places pointers to the vectors of
the given polygon in the sky array in the skycells immediately west
or south of each vector.

	The  sophisticated  INTREE  routine  is  complicated  by  the
proper  and efficient handling of  multi leveled holes.  If the given
polygon, named POLY, has a hole; and if that hole is deeper  than the
previous level; then there will  be two polygons associated with that
hole, lets  call them HOLE1 and HOLE2. Now HOLE2 being of the same
intensity level as Poly and  being an ENDO of Poly will has  not been
made yet; whereas HOLE1  has been  made and placed  in Exopoly's
ENDO ring. Thus INTREE must re-scan for the EXO's of all the polygons  on
Exopoly's ENDO ring.

On such rescanning there are  four cases:
	1. No change:	the scan returns Exopoly; which is the ENDO's
	   original EXO.
	2. Poly captures Endo; the scan returns Poly indicating
	   the Endo has been captured by POLY;
	3. My brothers fate; the ENDO hits an endo which
	   is not on the P-list.
	4. My fate delayed;

	Since deep holes frequently occur in natural images, (even in
images of pears and apples) I was amused to see that not a single deep
hole occurs in the examples in Krakauer's thesis which was about
nested polygon trees of video intensity contours.
PAGE 29. NESTING ILLUSTRATED. CONTINUED.
PAGE 30. NESTING CONTINUED.
PAGE 31. FIGURES: RECURSIVE SMOOTHING ILLUSTRATED.
PAGE 32. 4. SMOOTHING.

	In CRE and  GEOMED, the term  "smoothing" refers more  to the
problem  of breaking a  manifold up  into functions, rather  than the
problem of fitting functions to measured data.

	The smoothing step in CRE, converts the polygons  of vertical
and horizontal  vectors into  polygons of arcs.  For the  present the
term "arc"  means "linear arc" which is a line segment. Fancier arcs:
circular and cubic spline  were tried and found expensive  to compute
and unwieldly  to manipulate; however  fancy arcs were  doomed by the
fact that  after  going  to  all  the  trouble  of  implementing  and
computing them, there remained the overpowering  demand to break them
down again  into linear vectors for  computing areas, inertia tensors
or mere display buffers.

	To start, a ring  of two arcs is  formed (a bi-gon) with  one
arc at  the uppermost left  and the other  at the lowermost  right of
the  given  polygon  of  vectors.  Now  the  smoothing  operation  is
recursive; each arc  is in one  to one correspondece  with a list  of
vectors; if each point on  the list of vectors is close enough to the
approximating arc than  MKARC returns  the given arc  as goo  enough;
otherwise MKARC split  the arc in two and  place a new arc  vertex on
the vector vertex tht was furthest away from the original arc.

	This  manner of  smooth collaspes  the  stair cases  of jaggy
quantum edges.

PAGE 33. FIGURES: COMPARING ILLUSTRATED.

1ST Q3
2ND Q4
3RD FUSION Q3 AND Q4
4TH BABY.

PAGE 34. 5. COMPARING.

	The compare step of CRE connects the polygons and
arcs of the current image with corresponding polygons and arc
of the previous image. CMPARE solves the problem of correlating
features between two similar images.

CMPARE is composed of four sections: 

	1. make shape nodes for polygons.
	2. compare and connect polygons one to one.
	3. compare and connect polygons two to one.
	4. compare and connect vertices of two polygons.

 first shape nodes for
all the polygons of the current image are computed; second, the
polygons of each level of the current image are compared with
the corresponding level of the previous image for one to one match;
third, the unmated polygons of the current level aree compared with.
PAGE 35. LAMINA INERTIA TENSOR.
PAGE 36. PERFORMANCE.